package linklist;

import org.junit.Test;

import java.util.Stack;

//判断回文序列
public class LeetCode_234 {

    private class ListNode {
        int val;
        ListNode next;
        ListNode() {}
        ListNode(int val) { this.val = val; }
        ListNode(int val, ListNode next) { this.val = val; this.next = next; }
    }

    //判断回文序列
    public boolean isPalindrome(ListNode head) {
        return solution_2(head);
    }

    @Test
    public void test(){
        ListNode head1 = new ListNode(1, new ListNode(2, new ListNode(3, new ListNode(2, new ListNode(1)))));
        ListNode head2 = new ListNode(1, new ListNode(2, new ListNode(1, new ListNode(1))));
        System.out.println(solution_1(head1));
        System.out.println(solution_2(head2));
    }

    //利用栈实现
    public boolean solution_1(ListNode head) {
        ListNode temp = head;
        Stack<Integer> stack = new Stack<>();
        //1. 遍历链表，逐个将元素压入栈中
        while (temp!= null) {
            stack.push(temp.val);
            temp = temp.next;
        }

        //2. 在次遍历链表，逐个判断是否相等
        while (stack.size() > 0){
            if (head.val!= stack.pop()){
                return false;
            }
            head = head.next;
        }

        return true;
    }

    //利用快慢指针实现
    public boolean solution_2(ListNode head) {
         //1. 定义快慢指针，快指针2步，慢指针1步
        ListNode slow = head;
        ListNode fast = head;
        ListNode prev = null;

        //2. 快指针先走，慢指针后走
        while (true){
            if (fast==null){
                //慢指针处于0位置
                ListNode cur =  slow;
                prev.next=null;
                slow=null;
                while (cur!=null){
                    ListNode temp = cur.next;
                    cur.next=slow;
                    slow=cur;
                    cur=temp;
                }
                break;
            }
            if (fast.next==null){
                //慢指针处于1位置
                ListNode cur =  slow.next;
                slow.next=null;
                //修改后续指针
                while (cur!=null){
                    ListNode temp = cur.next;
                    cur.next=slow;
                    slow=cur;
                    cur=temp;
                }
                break;
            }
            fast = fast.next.next;
            prev = slow;
            slow = slow.next;

        }

        while (head != null && slow!=null){
            if (head.val!=slow.val){
                return false;
            }
            head=head.next;
            slow=slow.next;
        }

        return (head == null && slow ==null)? true : false;
    }


}
